/**
 * @Title:ImproveA.java
 * @Description:
   改进思路：
   当已经形成Combo后，如果后续移动Cost比当前还小的时候，可以直接抛弃。可以减少大量无用移动。
 * @author shan
 * @date 2015-4-8 上午8:48:29
 */
package com.shan.ai.combo.impl;

import java.util.List;

import com.shan.ai.combo.BaseCombo;
import com.shan.ai.combo.IComboConstant;
import com.shan.ai.combo.IComboConstant.BeadList;
import com.shan.ai.combo.IComboConstant.BeadType;
import com.shan.ai.combo.IComboConstant.Direct;
import com.shan.ai.combo.IComboConstant.Point;


/**
 * @author ShanSheng
 * 
 */
public class ImproveA extends BaseCombo {

    private double lastCost = -1;
    public long reduceCount = 0;
    /**
     * @param args
     */
    public static void main(String[] args) {
        ImproveA board = new ImproveA();

        long t1 = System.currentTimeMillis();

        // board.genRandomBoard();
        board.printBorad(board.initBeads);

        board.move(board.initBeads);

        // board.printList();

        board.printBorad(board.maxBeads);
        // board.computeCombo(board.maxBeads);

        long t2 = System.currentTimeMillis();

        System.out.println("Time(s):" + (t2 - t1));
        // System.out.println("Combo:" + board.comboList.size());
        System.out.println("Move:" + board.count + " Reduce:" + board.reduceCount);
        System.out.println("Cost(s):" + board.maxCost);

        for (int i = 0; i < board.maxStepList.size(); i++) {
            System.out.print(board.maxStepList.get(i) + "->");
        }

        System.out.println();

        for (BeadList combo : board.maxcomboList) {
            for (int i = 0; i < combo.size(); i++) {
                System.out.print(combo.get(i) + "->");
            }
            System.out.println();
        }
        
//        ScreenCapUtils.drawLines(board.maxStepList);

    }
    
 
    @Override
    public List<Point> move(BeadType[][] initBeads) {
        startTime = System.currentTimeMillis();


        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COLUMN; j++) {

                runTimeBeads = copyBoard(initBeads);

                Point startPoint = new Point(i, j);
                stepList.clear();
                stepList.add(startPoint);
                lastCost = -1;
                moveIn();
                if (bFinalStop) {
                    return maxStepList;
                }
//                bOnceStop = false;

            }
        }
        
        System.out.println("Move over");
        return maxStepList;
    }
    
    public void moveIn() {

        if (bFinalStop ) {
            return;
        }

        // 终止条件满足
        if (isEndCondition()) {
            bFinalStop = true;
            return;
        }

        if (stepList.size() >= MAX_STEP) {
//            bOnceStop = true;
            moveBack();
            return;
        }

        Point currPoint = stepList.get(stepList.size() - 1);

        
        for (Direct direct : Direct.values()) {

            double currCost = moveAndcost(currPoint, direct);
            // printList();
            if (currCost >= 0 && (currCost >= lastCost )) {
                lastCost = currCost;
                moveIn();
                if (bFinalStop) {
                    return;
                }
                // resetBoard();
            }else if(currCost >= 0){
                moveBack();
                reduceCount++;
            }

        }

        moveBack() ;
        return;
    }
    
    public void moveBack() {
        lastCost = -1;
        if (stepList.size() < 2) {
            // bOnceStop = true;
            return;
        }
        Point from = stepList.remove(stepList.size() - 1);
        Point to = stepList.get(stepList.size() - 1);

        BeadType temp = runTimeBeads[from.x][from.y];
        runTimeBeads[from.x][from.y] = runTimeBeads[to.x][to.y];
        runTimeBeads[to.x][to.y] = temp;
    }
    
    public double computeCost(List<BeadList> comboList) {
        double cost = 0;
        double p1 = (1 + (comboList.size() - 1) * 0.25);
        int count = 0;
        for (BeadList beadList : comboList) {
            count += beadList.size() - 3;
        }
        double p2 = comboList.size() + count * 0.25;
        cost = p1 * p2;

        return cost;
    }

}
